package 算法.回溯法.n皇后问题;


import java.util.Scanner;


public class N皇后问题_满n叉树2 {
    public static void main(String[] args) {
        System.out.print("请N皇后问题得N的个数：");
        Scanner scanner = new Scanner(System.in);
        // int max = 8;//max表示n个皇后
        int max = scanner.nextInt();
    //        用array[n]表示：皇后在第n+1行,array[n]列。比如array[0] = 8
    //        意思为:该皇后位于第1行第8列的坐标;
        int array[] = new int[max];

        new N皇后问题_满n叉树2().backtrack(0,max,array);
    }
     //核心代码
        public void backtrack(int n,int max,int []array) {
            if (n == max) {//层数：n,从零开始。  深度：max 。 n==max表示遍历完叶子节点
                print(array,max);
                return;
            } else {
                for (int i = 1; i <=max; i++) {//第n层的第i列，要明白当前属于是哪一层！ 即搜索或回溯到了哪一层了！
                    array[n] =i;//array[n]表示的就是第n层第i列，即皇后的坐标
                    if (nice(n,array)) {
                        backtrack(n + 1,max,array);//类似于n重for循环，只不过变成递归版的
                    }
                }
            }

        }

        public boolean nice(int n,int []array) {
            for (int i = 0; i < n; i++) {//前i层: 跟之前已经确定的 皇后的位置进行比较
             //   System.out.println(array[i]==(i+1));
                if (Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                   // if (array[n]==array[i])
//                    if (n!=i)
                     return false;
                }
                if(array[i]==array[n]){//保证了列值的不重复
                    return false;
                }
            }
            return true;
        }
        int k = 0;
        public void print(int []array,int max) {
            ++k;
            System.out.print("第" + k + "种解法:");
            for (int i = 0; i < array.length; i++) {
                System.out.print("("+(i+1)+","+array[i]+")");
                // System.out.print(array[i] + " ");
            }
            System.out.println();

            int[][] a=new int[max][max];
            for (int i = 0; i <max ; i++) {
                int b=array[i]-1;
                for (int j = 0; j <max ; j++) {
                    if (j==b){
                        a[i][j]=1;
                    }
                    System.out.print(a[i][j]);
                }
                System.out.println();
            }
        }
}
